package org.datacoder.geocoding.datastructures.points

import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.*
import org.datacoder.util.*

class SortedArray {

    private static final int BINARY_SEARCH_LIMIT = 50
    GeoPoint[] geoPoints
    int type

    public SortedArray(Collection<Jurisdiction> jurisdictions, int type){
        this.type = type
        geoPoints = new GeoPoint[jurisdictions.size()]
        int i = 0
        for(juris in jurisdictions){
            geoPoints[i++] = juris.toGeoPoint()
        }
        Arrays.sort(geoPoints, new GeoPointComparator(type))
    }
    public SortedArray(GeoPoint[] parentGeoPoints, int startIndex, int endIndex, int type){
        this.type = type
        geoPoints = Arrays.copyOfRange(parentGeoPoints, startIndex, endIndex)
        Arrays.sort(geoPoints, new GeoPointComparator(type))
    }

    public Set<Jurisdiction> findPointsWithinInterval(GeoInterval gi){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        findPointsWithinInterval(gi, jurisdictions)
        return jurisdictions
    }
    public void findPointsWithinInterval(GeoInterval gi, Set<Jurisdiction> jurisdictions){
        if(geoPoints.length < BINARY_SEARCH_LIMIT){
            boolean lowerBoundFound = false
            int i = 0
            double minValue = gi.retrieveMinDoubleValue()
            double maxValue = gi.retrieveMaxDoubleValue()
            while(i < geoPoints.length){
                if(geoPoints[i].retrieveValue(type) >= minValue){
                    lowerBoundFound = true
                    break
                }
                i++
            }
            if(!lowerBoundFound){
                return
            }
            while((i < geoPoints.length) && (geoPoints[i].retrieveValue(type) <= maxValue)){
                jurisdictions.add(geoPoints[i++].juris)
            }
        }else{
            int startIndex = retrieveFirstGreaterIndex(gi.retrieveMinDoubleValue())
            int endIndex = retrieveLastLesserIndex(gi.retrieveMaxDoubleValue())
            if((startIndex != -1) && (endIndex != -1)){
                for(int i = startIndex; i <= endIndex; i++){
                    jurisdictions.add(geoPoints[i].juris)
                }
            }
        }
    }

    public int retrieveFirstGreaterIndex(double val){
        int min = 0
        int max = geoPoints.length
        if(max == 0){
            return -1
        }
        int middle = (min + max)/2
        while(true){
            double middleVal = geoPoints[middle].retrieveValue(type)
            if(middleVal == val){           // Found!
                int i = middle - 1
                while(i > 0){               // Make sure returning first instance
                    if(geoPoints[i].retrieveValue(type) == val){
                        middle = i
                    }else{
                        return middle
                    }
                    i--
                }
                return 0
            }else if(middleVal < val){      // Undershot?
                if(middle == (geoPoints.length - 1)){
                    return -1               // Entire set is below target value
                }else if(geoPoints[middle + 1].retrieveValue(type) > val){
                    return middle + 1
                }else if(max <= (min + 1)){
                    return -1
                }else{
                    min = middle
                    middle = (min + max)/2
                    continue
                }
            }else{                          // Overshot
                if(middle == 0){
                    return 0                // Entire set is above target value
                }else{
                    max = middle
                    middle = (min + max)/2
                    continue
                }
            }
        }
    }
    public int retrieveLastLesserIndex(double val){
        int length = geoPoints.length
        int min = 0
        int max = length
        if(max == 0){
            return -1
        }
        int middle = (min + max)/2
        while(true){
            double middleVal = geoPoints[middle].retrieveValue(type)
            if(middleVal == val){           // Found!
                int i = middle + 1
                while(i < length){          // Make sure returning first instance
                    if(geoPoints[i].retrieveValue(type) == val){
                        middle = i
                    }else{
                        return middle
                    }
                    i++
                }
                return 0
            }else if(middleVal < val){      // Undershot
                if(middle == (geoPoints.length - 1)){
                    return geoPoints.length - 1 // Entire set is below target value
                }else if(max <= (min + 1)){
                    return -1
                }else{
                    min = middle
                    middle = (min + max)/2
                    continue
                }
            }else{                          // Overshot?
                if(middle == 0){
                    return -1               // Entire set is above target value
                }else if(geoPoints[middle - 1].retrieveValue(type) < val){
                    return middle - 1
                }else{
                    max = middle
                    middle = (min + max)/2
                    continue
                }
            }
        }
    }
}